/*
 * One example for NOI CSP-J Lesson 7:
 * <https://courses.fmsoft.cn/plzs/noijunior-graph-and-graph-theory.html>
 *
 * Author: Vincent Wei
 *  - <https://github.com/VincentWei>
 *  - <https://gitee.com/vincentwei7>
 *
 * Copyright (C) 2025 FMSoft <https://www.fmsoft.cn>.
 * License: GPLv3
 */
#include <iostream>           // for std::cout
#include <utility>            // for std::pair
#include <vector>             // for std::vector
#include <stack>              // for std::stack

using namespace std;

using adj_list = vector<vector<int>>;

// 该函数执行 DFS 和拓扑排序
static void
topo_sort_helper(int v, adj_list &dag, vector<bool> &visited, stack<int> &st)
{
    // 标记当前顶点为已访问。
    visited[v] = true;

    // 对当前顶点的所有未访问邻接顶点进行递归处理
    for (int i : dag[v]) {
        if (!visited[i])
            topo_sort_helper(i, dag, visited, st);
    }

    // 将当前顶点压入结果栈
    st.push(v);
}

// 该函数拓扑排序的入口函数
vector<int> topo_sort(adj_list &dag)
{
    // 用于保存结果的栈
    stack<int> st;

    // 用于记录顶点是否已访问的数组（矢量）
    vector<bool> visited(dag.size(), false);

    // 对每个未访问的顶点依次调用 topo_soft_helper() 函数进行递归处理。
    for (size_t i = 0; i < dag.size(); i++) {
        if (!visited[i])
            topo_sort_helper(i, dag, visited, st);
    }

    vector<int> ans;

    // 将栈中元素依次弹出并保存到 ans 中
    while (!st.empty()) {
        ans.push_back(st.top());
        st.pop();
    }

    return ans;
}

int main()
{
    // 使用 pair<int, int> 定义边构成的数组
    pair<int, int> edges[] = {
        {2, 3},
        {3, 1},
        {4, 0},
        {4, 1},
        {5, 0},
        {5, 2}
    };

    // 注意 sizeof() 的用法
    vector<vector<int>> dag(sizeof(edges)/sizeof(edges[0]));

    // 构造有向图
    for (auto it : edges) {
        dag[it.first].push_back(it.second);
    }

    // 获取拓扑排序
    vector<int> ans = topo_sort(dag);

    // 输出拓扑排序
    for (auto node : ans) {
        cout << node << " ";
    }
    cout << endl;

    return 0;
}

